package linkedlist;

/**
 * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
 * 这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 * 给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
 */
class Node{
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
public class no430 {
    public Node flatten(Node head) {
        if (head == null || (head.next == null && head.child == null)){
            return head;
        }
        Node cur = head;
        Node MiddleTail = null;
        Node newNode = null;
        while (cur != null){
            if(cur.child == null){
                if(cur.next == null){
                    MiddleTail = cur;
                }
                cur = cur.next;
            }else{
                if(cur.next == null){
                    MiddleTail = cur;
                }
                Node temp = cur.next;
                if(temp != null){
                    temp.prev = null;
                    if(newNode == null){
                        newNode = temp;
                    }else{
                        Node tail = temp;
                        while (tail.next != null){
                            tail = tail.next;
                        }
                        tail.next = newNode;
                        newNode.prev = tail;
                        newNode = temp;
                    }
                }
                Node node = cur.child;
                cur.next = node;
                node.prev = cur;
                cur.child = null;
                cur = cur.next;
            }
        }
        if (newNode != null){
            MiddleTail.next = newNode;
            newNode.prev = MiddleTail;
        }
        return head;
    }
}
